from typing import Literal, Sequence, Self
from numpy.typing import NDArray
import numpy as np

__epsilon = 10e-5

class Vec2:
    def __init__(self, x: float, y: float) -> None:
        self.x = x
        self.y = y
    
    def __getitem__(self, value: Literal[0, 1]) -> float:
        if value == 0: return self.x
        if value == 1: return self.y
    
    def __add__(self, other: Self) -> "Vec2":
        return Vec2(self.x + other[0], self.y + other[1])
    
    def __sub__(self, other: Self) -> "Vec2":
        return Vec2(self.x - other[0], self.y - other[1])
    
    def __mul__(self, other: int | float | Sequence[float]) -> "Vec2":
        if isinstance(other, (int, float)):
            return Vec2(self.x * other, self.y * other)
        return Vec2(self.x * other[0], self.y * other[1])
    
    def __truediv__(self, other: int | float | Sequence[float]) -> "Vec2":
        if isinstance(other, (int, float)):
            return Vec2(self.x / other, self.y / other)
        return Vec2(self.x / other[0], self.y / other[1])
    
    def __str__(self) -> str:
        return f"Vec2({self.x}, {self.y})"
    
    def __repr__(self) -> str:
        return self.__str__()
    
    def __array__(self) -> NDArray[np.float64]:
        return np.array([self.x, self.y])
    
    def __lt__(self, other: "Vec2") -> bool:
        if self.x < other.x:
            return True
        if self.x > other.x:
            return False
        return self.y < other.y
    
    @property
    def xy(self) -> tuple[float, float]:
        return (self.x, self.y)
    
    def round(self, ndigits: int) -> "Vec2":
        return Vec2(
            round(self.x, ndigits),
            round(self.y, ndigits)
        )
    
    def rotate(self, degrees: float) -> "Vec2":
        rad = np.deg2rad(degrees)
        return Vec2(
            self.x * np.cos(rad) - self.y * np.sin(rad),
            self.y * np.cos(rad) + self.x * np.sin(rad)
        )
    
    def cross(self, other: "Vec2") -> float:
        return self.x * other.y - self.y * other.x

def cross(O: Vec2, A: Vec2, B: Vec2) -> float:
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x)

def get_center(vertices: Sequence[Vec2], ndigits: int | None = None) -> Vec2:
    center: Vec2 = sum(vertices, Vec2(0, 0)) / len(vertices)
    if ndigits is None:
        return center
    return center.round(ndigits)

def get_convex_hull(vertices: Sequence[Vec2]) -> list[Vec2]:
    vert: list[Vec2] = []
    for v in vertices:
        flag = True
        for vi in vert:
            if (abs(vi.x - v.x) < __epsilon) and (abs(vi.y - v.y) < __epsilon):
                flag = False
                break
            
        if flag:
            vert.append(v)
    
    vert = sorted(vert)
    
    lower: list[Vec2] = []
    for v in vert:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], v) <= 0:
            lower.pop()
        lower.append(v)
        
    upper: list[Vec2] = []
    for v in reversed(vert):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], v) <= 0:
            upper.pop()
        upper.append(v)
    
    return lower[:-1] + upper[:-1]

def polygon_area(vertices: Sequence[Vec2]) -> float:
    area = 0
    
    prev = vertices[-1]
    for vt in vertices:
        area += vt.x * prev.y - vt.y * prev.x
        prev = vt
    
    return abs(area / 2)